# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        leftNums = 0
        if root.left:
            leftNums = self.getRootNums(root.left)
        if k == leftNums + 1:
            return root.val
        elif k <= leftNums:
            return self.kthSmallest(root.left, k)
        else:
            return self.kthSmallest(root.right, k - 1 - leftNums)

    def getRootNums(self, root: TreeNode):
        if root is None:
            return 0
        return self.getRootNums(root.left) + self.getRootNums(root.right) + 1


if __name__ == '__main__':
    so = Solution()
    s = [1, 1, 1, 3, 3, 2, 2, 2]
    r = so.majorityElement(s)
    print(r)
